package Backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/*
* 39.组合总数
*
* result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
* */
public class CombinationSum39 {
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,target,0,new LinkedList<>(),0);
        return res;
    }

    private void dfs(int[] candidates, int target, int sum,LinkedList<Integer> list,int start){
        if(sum==target){
            res.add(new LinkedList<>(list));
            return;
        }
        for(int i=start;i<candidates.length;i++){
            if(target-sum<candidates[i]){
                break;
            }
             //去除重复的集合, 下面这句跟传入一个start效果一样
            // 这一句没搞懂
//            if(list.size() > 0 && list.get(list.size() - 1) > candidates[i]) {
//                continue;
//            }
            sum+=candidates[i];
            list.addLast(candidates[i]);
            dfs(candidates,target,sum,list,i);
            sum-= list.getLast();
            list.removeLast();
        }
    }
    public void test(){
        List<List<Integer>> lists = combinationSum(new int[]{2, 3, 6, 7}, 7);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }

}
